import java.util.*;
public class Solution {
    //JZ66 构建乘积数组(暴力)
/*
    public int[] multiply(int[] A) {
        int[] ret = new int[A.length];
        //先给数组初始化成全1
        for(int i = 0; i < ret.length; i++){
            ret[i] = 1;
        }
        for(int i = 0; i < A.length; i++){
            for(int j = 0; j < A.length; j++){
                if(j == i){
                    continue;
                }else{
                    ret[i] *= A[j];
                }
            }
        }
        return ret;
    }
*/
    //JZ66 构建乘积数组（优化1）
    public int[] multiply(int[] A) {
        int[] ret = new int[A.length];
        //先给数组初始化成全1
        for(int i = 0; i < A.length; i++){
            ret[i] = 1;
            for(int j = 0; j < A.length; j++){
                if(j == i){
                    continue;
                }else{
                    ret[i] *= A[j];
                }
            }
        }
        return ret;
    }
    //JZ50 第一个只出现一次的字符
    public int FirstNotRepeatingChar(String str) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        int len = str.length();
        for(int i = 0; i < len; i++){
            //一旦有重复的Key，value值就设为2
            if(hashMap.containsKey(str.charAt(i))){
                hashMap.put(str.charAt(i), 2);
            }else{
                hashMap.put(str.charAt(i), 1);
            }
        }
        //通过遍历str对比哈希表中的value
        for(int i = 0; i < len; i++){
            if(hashMap.get(str.charAt(i)) == 1){
                return i;
            }
        }
        return -1;
    }
    //JZ5 替换空格
    public String replaceSpace (String s) {
        StringBuilder str = new StringBuilder();
        int len = s.length();
        for(int i = 0; i < len; i++){
            if(s.charAt(i) == ' '){
                str.append("%20");
            }else{
                str.append(s.charAt(i));
            }
        }
        return str.toString();
    }
    //JZ39 数组中出现次数超过一半的数字(模拟哈希法)
    public int MoreThanHalfNum_Solution(int [] array) {
        int len = array.length;
        int[] tmpArr = new int[10001];
        //用哈希法，给每一位都统计出现的次数
        for(int i = 0; i < len; i++){
            tmpArr[array[i]]++;
        }
        //找出超出一半的数字
        for(int i = 0; i < len; i++){
            if(tmpArr[array[i]] > len / 2){
                return array[i];
            }
        }
        return -1;
    }
    //JZ39 数组中出现次数超过一半的数字(HashMap法，开销比刚刚的模拟哈希法大，但是比他更通用)
/*    public int MoreThanHalfNum_Solution(int [] array) {
        HashMap<Integer, Integer> hash = new HashMap<>();
        int len = array.length;
        for(int i = 0; i < len; i++){
            //若没出现过，value设置为一，若出现过，value+1
            if(!hash.containsKey(array[i])){
                hash.put(array[i], 1);
            }else{
                hash.put(array[i], hash.get(array[i]) + 1);
            }
        }
        //遍历查找过半元素
        for(int i = 0; i < len; i++){
            if(hash.get(array[i]) > len / 2){
                return array[i];
            }
        }
        return -1;
    }*/
    //JZ43 整数中1出现的次数
    public int NumberOf1Between1AndN_Solution(int n) {
        int count = 0;
        //产生1 ~ n个数字
        for(int i = 1; i <= n; i++){
            int tmp = i;
            while(tmp != 0){
                if(tmp % 10 == 1){
                    count++;
                }
                tmp /= 10;
            }
        }
        return count;
    }
    //JZ45 把数组排成最小的数
    public String PrintMinNumber(int [] numbers) {
        int len = numbers.length;
        if(numbers == null || len == 0){
            return "";
        }
        String[] str = new String[len];
        for(int i = 0; i < len; i++){
            str[i] = String.valueOf(numbers[i]);
        }
        Arrays.sort(str, new Comparator<String>(){
           public int compare(String o1, String o2){
               return (o1 + o2).compareTo(o2 + o1);
           }
        });
        //拼接起来
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i < len; i++){
            ret.append(str[i]);
        }
        return ret.toString();
    }
    //JZ49 丑数(暴力,超时)
/*    public int GetUglyNumber_Solution(int index) {
        //统计丑数个数
        int count = 1;
        //记录自然数
        int n = 1;
        //首先除2，直到不能整除为止，然后除5到不能整除为止，然后除3直到不能整除为止。
        //最终判断剩余的数字是否为1，如果是1则为丑数，否则不是丑数。
        while(count <= 2000){
            if(index == count){
                return n;
            }
            n++;
            //用tmp来判断是否为丑数
            int tmp = n;
            while(tmp % 2 == 0){
                tmp /= 2;
            }
            while(tmp % 3 == 0){
                tmp /= 3;
            }
            while(tmp % 5 == 0){
                tmp /= 5;
            }
            //判断是否为丑数
            if(tmp == 1){
                count++;
            }
        }
        return n;
    }*/
    //JZ49 丑数
    public int GetUglyNumber_Solution(int index) {
        //优化0123456
        if(index <= 6){
            return index;
        }
        int[] array = new int[index];
        //用来标记三个位置
        int i1 = 0;
        int i2 = 0;
        int i3 = 0;
        array[0] = 1;
        for(int i = 1; i < index; i++) {
            //下一个丑数从2^x*3^y*5^z中找
            array[i] = Math.min(array[i1]*2, Math.min(array[i2]*3, array[i3]*5));
            //下一次乘以倍数的就是最小的那一个
            if(array[i] == array[i1]*2){
                i1++;
            }
            if(array[i] == array[i2]*3){
                i2++;
            }
            if(array[i] == array[i3]*5){
                i3++;
            }
        }
        return array[index - 1];
    }
    //JZ58 左旋转字符串
    public String LeftRotateString(String str,int n) {
        //先转换成字符数组
        char[] array = str.toCharArray();
        int len = array.length;
        //优化
        if(n > len){
            len %= n;
        }
        //冒泡法
        for(int i = 0; i < n; i++){
            for(int j = 0; j < len - 1; j++){
                swap(array, j, j + 1);
            }
        }
        //拼接成字符串
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i < len; i++){
            ret.append(array[i]);
        }
        return ret.toString();
    }
    private void swap(char[] array, int i, int j){
        char tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    //JZ74 和为S的连续正数序列(穷举)
/*    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> retArr = new ArrayList<>();
        //从零开始向后穷举
        for(int i = 1; i < sum; i++){
            //先建立一个临时顺序表，把所有可能先放进去，最后满足要求再放入retArr
            ArrayList<Integer> array = new ArrayList<>();
            for(int j = i; j < sum; j++){
                //每次求一遍和,看是否满足sum
                array.add(j);
                int s = getSum(array);
                if(s == sum){
                    //若满足要求，则加入到retArr
                    retArr.add(array);
                    break;
                }
            }
        }
        return retArr;
    }
    //求和
    private int getSum(ArrayList<Integer> array){
        int len = array.size();
        int sum = 0;
        for(int i = 0; i < len; i++){
            sum += array.get(i);
        }
        return sum;
    }*/
    //JZ74 和为S的连续正数序列(求和等差数列优化)
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> retArr = new ArrayList<>();
        //从零开始向后穷举
        for(int i = 1; i < sum; i++){
            //先建立一个临时顺序表，把所有可能先放进去，最后满足要求再放入retArr
            ArrayList<Integer> array = new ArrayList<>();
            for(int j = i; j < sum; j++){
                //每次求一遍和,看是否满足sum
                array.add(j);
                int s = getSum(array);
                if(s == sum){
                    //若满足要求，则加入到retArr
                    retArr.add(array);
                    break;
                }
            }
        }
        return retArr;
    }
    //求和
    private int getSum(ArrayList<Integer> array){
        int len = array.size();
        //因为是连续的，所以可以用等差数列求和公式优化
        return (array.get(0) + array.get(len - 1)) * len / 2;
    }
    //JZ74 和为S的连续正数序列(滑动窗口)
    public ArrayList<ArrayList<Integer> > FindContinuousSequence3(int sum) {
        ArrayList<ArrayList<Integer>> retArr = new ArrayList<>();
        //滑动窗口的左右指针
        int left = 1;
        int right = 2;
        while(left != right) {
            ArrayList<Integer> array = new ArrayList<Integer>();
            //计算滑动窗口序列和是否为sum(等差数列求和)
            int tmpSum = (left + right) * (right - left + 1) / 2;
            if(tmpSum == sum) {
                //如果是则放入array,再放入到retArr
                for(int i = left; i <= right; i++){
                    array.add(i);
                }
                retArr.add(array);
                right++;
                left++;
            }else if(tmpSum < sum){
                //小于和，则将right向右扩展
                right++;
            }else{
                //大于和，则向left向右缩小
                left++;
            }
        }
        return retArr;
    }

    public ArrayList<Integer> FindNumbersWithSum1(int [] array,int sum) {
        ArrayList<Integer> retArr = new ArrayList<>();
        int len = array.length;
        //数组长度小于等于1，即不存在
        if(len <= 1){
            return retArr;
        }
        //滑动窗口左右指针
        int left = 0;
        int right = 1;
        //窗口大小为1，即找完
        while(right < len && left != right){
            int s = fundSum(array, left, right);
            if(s == sum){
                //找到了,放入顺序表
                for(int i = left; i <= right; i++){
                    retArr.add(array[i]);
                }
                break;
            }else if(s < sum){
                //若小于，则让right窗口边界向右扩增
                right++;
            }else{
                //若大于，则让left窗口边界向右缩小
                left++;
            }
        }
        return retArr;
    }
    //计算和
    private int fundSum(int[] array, int left, int right){
        int sum = 0;
        for(int i = left; i <= right; i++){
            sum += array[i];
        }
        return sum;
    }
    //JZ57 和为S的两个数字(暴力)
/*    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> retArr = new ArrayList<>();
        int len = array.length;
        if(len <= 1){
            return retArr;
        }
        for(int i = 0; i < len - 1; i++) {
            for(int j = i + 1; j < len; j++) {
                if(array[i] + array[j] == sum){
                    retArr.add(array[i]);
                    retArr.add(array[j]);
                    return retArr;
                }
            }
        }
        return retArr;
    }*/
    //JZ57 和为S的两个数字(双指针夹击)
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> retArr = new ArrayList<>();
        int len = array.length;
        if(len <= 1){
            return retArr;
        }
        //双指针,向中间夹击
        int start = 0;
        int end = len - 1;
        while(start < end){
            int s = array[start] + array[end];
            if(s == sum){
                //找到了
                retArr.add(array[start]);
                retArr.add(array[end]);
                return retArr;
            }else if(s < sum){
                //小了，就让left向右走，值就可以扩大
                start++;
            }else{
                //大了，就让right向左走，值就可以缩小
                end--;
            }
        }
        return retArr;
    }
    //JZ62 孩子们的游戏(圆圈中最后剩下的数)
    public int LastRemaining_Solution(int n, int m) {
        if(n == 0 || m == 0){
            return -1;
        }
        //递推公式
        int x = 0;
        for(int i = 2; i <= n; i++){
            x = (x + m) % i;
        }
        return x;
    }
    //JZ75 字符流中第一个不重复的字符(map法)
    //Insert one char from stringstream
    HashMap<Character, Integer> map = new HashMap<>();
    ArrayList<Character> array = new ArrayList<>();
    public void Insert(char ch)
    {
        //顺序表中保留字符流，方便后序遍历查找第一个不重复的字符
        array.add(ch);
        //放入map中并统计次数
        if(!map.containsKey(ch)){
            map.put(ch, 1);
        }else{
            //用2来表示多次
            map.put(ch, 2);
        }

    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        int len = array.size();
        for(int i = 0; i < len; i++){
            if(map.get(array.get(i)) == 1){
                return array.get(i);
            }
        }
        return '#';
    }
}
